1. Field of the Invention
The present invention relates to placement in integrated circuit design.
2. State of the Art
The physical design of integrated circuits involves placement of gates within a design layout, representing a physical integrated circuit, and routing of interconnections (nets) between gates. The logical integrated circuit design is represented in the form of a netlist, i.e., a list of gates or collections of gates (tnacros) and nets interconnecting them. A graph representation of a netlist is shown in FIG. 1A. Through placement and routing, the logical integrated circuit design is translated to a physical integrated circuit design. Placement and routing are performed using Electronic Design Automation (EDA) software tools running on powerful computers.
Placement and routing are closely inter-related. As integration density increases, the sheer size of integrated circuit designs challenges current methods of physical design. Furthermore, physical design is required to be more exacting in order to avoid deleterious interactions and to ensure that all design constraints are met.
A number of approaches to the placement problem have been proposed, including simulated annealing, genetic algorithms, mathematical/linear programming, bisection type approaches, etc. One widely-practiced partitioning algorithm known as FM after its originators Fiduccia and Matheyses, is used as the basis for many placement algorithms. In FM, groups of features are formed, and features are exchanged between the groups so as to minimize the number of nets extending between the groups. The FM technique, an example of a module partitioning heuristic, may be represented as follows:                1. Determine initial partition of modules. 2. Loop until no more improvement in the partition results, or until a maximum number of passes is tried:                    a. Free all modules and compute module gains.            b. Loop while there remains a free module that can be moved:                            i. Select next module to be moved (select free module of maximum gain, subject to area-balance criterion).                ii. Move selected module to opposite side of partition.                iii. Update module gains.                                    c. Reconstruct best partition of pass.                        
Gain refers to decrease in the number of nets crossing between opposite sides of the partition.
A major shortcoming of the foregoing technique, as well as other similar techniques, is that after a partition has been made, it is difficult or impossible for gates or modules to cross the partition boundary. This restriction often results in inferior placements. A cycling and overlapping partitioning process is described in Huang and Kahng, Partitioning-Based Standard Cell with an Exact Objective, Proc. of the International Symposium on Physical Design, April 1997. This approach, to a limited extent, does allow gates and modules to cross partition boundaries. However, the approach is not cluster-based (is slow) and does not exploit the full power of cycling and overlapping partitioning (produces less-than-adequate quality).
In short, none of these existing placement techniques appears well-equipped to meet the challenges of the deep sub-micron era.